'''
https://leetcode.cn/problems/verify-preorder-sequence-in-binary-search-tree
'''
from math import inf
from typing import List


class Solution:
    def verifyPreorder(self, preorder: List[int]) -> bool:
        def f(l, r):
            if l >= r:
                return True
            mid = l + 1
            while mid <= r and preorder[mid] <= preorder[l]:
                mid += 1
            res = True
            for t in range(mid, r + 1):
                if preorder[t] < preorder[l]:
                    res = False
                    break
            res = res and f(l + 1, mid - 1) and f(mid, r)
            return res

        return f(0, len(preorder) - 1)

    def verifyPreorder2(self, preorder: List[int]) -> bool:
        def f(l, r):
            if l > r:
                return True, float('inf'), float('-inf')
            if l == r:
                return True, preorder[l], preorder[l]
            mid = l + 1
            while mid <= r and preorder[mid] <= preorder[l]:
                mid += 1

            l_ans, l_min, l_max = f(l + 1, mid - 1)
            r_ans, r_min, r_max = f(mid, r)
            cur = preorder[l]
            ans = l_ans and r_ans and l_max < cur < r_min
            minv = min(l_min, r_min, cur)
            maxv = min(l_max, r_max, cur)
            return ans, minv, maxv

        return f(0, len(preorder) - 1)[0]

    def verifyPreorder3(self, preorder: List[int]) -> bool:
        stack = []
        min_val = float('-inf')
        for num in preorder:
            if num <= min_val:
                return False
            while stack and num > stack[-1]:
                # 当来到一颗子树的右节点，pop出这个树上的根节点和所有左边节点
                min_val = stack.pop()
            stack.append(num)
        return True


preorder = [5,2,1,3,6]
print(Solution().verifyPreorder3(preorder))